package com.study.zgw.juc;

import java.util.ArrayList;
import java.util.List;

/**
 * 位图（Bitmap）是一种用于实现数据去重的高效数据结构
 */
public class Bitmap {

    private byte[] bits;
    private int size;

    public Bitmap(int size) {
        this.size = size;
        // 计算需要的字节数
        bits = new byte[(size >> 3) + 1];
    }


    public void add(int num) {
        if (num >= 0 && num < size) {
            int byteIndex = num >> 3;
            int bitIndex = num & 7;
            bits[byteIndex] |= (1 << bitIndex);
        }
    }

    public boolean contains(int num) {
        if (num >= 0 && num < size) {
            int byteIndex = num >> 3;
            int bitIndex = num & 7;
            return (bits[byteIndex] & (1 << bitIndex))!= 0;
        }
        return false;
    }

    public static void main(String[] args) {
        Bitmap bitmap = new Bitmap(100);  // 假设处理0-99的整数
        List<Integer> inputList = new ArrayList<>();
        inputList.add(10);
        inputList.add(20);
        inputList.add(10);  // 重复元素
        inputList.add(30);

        for (int num : inputList) {
            bitmap.add(num);
        }

        for (int i = 0; i < 40; i++) {
            if (bitmap.contains(i)) {
                System.out.println(i + " 存在于位图中，已被标记");
            }
        }
    }

}
